#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/8 11:07
# @USER    : Shengji He
# @File    : SatisfiabilityEqualityEquations.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class UnionField:
    def __init__(self):
        self.parent = list(range(26))

    def find(self, index):
        if index == self.parent[index]:
            return index
        self.parent[index] = self.find(self.parent[index])
        return self.parent[index]

    def union(self, index1, index2):
        self.parent[self.find(index1)] = self.find(index2)


class Solution:
    def equationsPossible(self, equations: List[str]) -> bool:
        """
        Given an array equations of strings that represent relationships between variables,
        each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b".
        Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

        Return true if and only if it is possible to assign integers to variable names
        so as to satisfy all the given equations.

        Example 1:
            Input: ["a==b","b!=a"]

            Output: false

            Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
            There is no way to assign the variables to satisfy both equations.

        Example 2:
            Input: ["b==a","a==b"]

            Output: true

            Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

        Example 3:
            Input: ["a==b","b==c","a==c"]

            Output: true

        Example 4:
            Input: ["a==b","b!=c","c==a"]

            Output: false

        Example 5:
            Input: ["c==c","b==d","x!=z"]

            Output: true

        Note:
            - 1 <= equations.length <= 500
            - equations[i].length == 4
            - equations[i][0] and equations[i][3] are lowercase letters
            - equations[i][1] is either '=' or '!'
            - equations[i][2] is '='

        :param equations: List[str]
        :return: bool
        """
        # equal = defaultdict(list)
        # inequal = defaultdict(list)
        # for ele in equations:
        #     if ele[0] == ele[3]:
        #         if ele[1] == '!':
        #             return False
        #     else:
        #         if ele[1] == '=':
        #             if equal.get(ele[0]) and ele[3] in equal.get(ele[0]):
        #                 continue
        #             eles = [ele[0], ele[3]]
        #             if equal.get(ele[0]):
        #                 eles += equal.get(ele[0])
        #             if equal.get(ele[3]):
        #                 eles += equal.get(ele[3])
        #             for i in range(len(eles)):
        #                 equal[eles[i]].extend(eles[:i] + eles[i + 1:])
        #                 equal[eles[i]] = list(set(equal[eles[i]]))
        #
        #                 if inequal.get(eles[i]) and \
        #                         sum([True if j in inequal[eles[i]] else False for j in equal[eles[i]]]) > 0:
        #                     return False
        #                 elif inequal.get(eles[i]):
        #                     for j in equal[eles[i]]:
        #                         inequal[j].extend(inequal[eles[i]])
        #                         inequal[j] = list(set(inequal[j]))
        #                     for j in inequal[eles[i]]:
        #                         inequal[j].extend(equal[eles[i]])
        #                         inequal[j] = list(set(inequal[j]))
        #
        #         else:
        #             if inequal.get(ele[0]) and ele[3] in inequal[ele[0]]:
        #                 continue
        #
        #             inequal[ele[0]].extend([ele[3]])
        #             inequal[ele[3]].extend([ele[0]])
        #             if equal.get(ele[0]) and ele[3] in equal[ele[0]]:
        #                 return False
        # return True
        equations.sort(key=lambda x: x[1], reverse=True)
        uf = UnionField()
        for st in equations:
            index1 = ord(st[0]) - ord('a')
            index2 = ord(st[3]) - ord('a')
            if st[1] == '=':
                uf.union(index1, index2)
            elif uf.find(index1) == uf.find(index2):
                return False
            else:
                pass
        return True


if __name__ == '__main__':
    S = Solution()
    # equations = ["b==a","a==b"]
    # equations = ["a==b","b==c","a==c"]
    # equations = ["a==b", "b!=c", "c==a"]
    # equations = ["a==b","e==c","b==c","a!=e"]
    equations = ["f==a","a==b","f!=e","a==c","b==e","c==f"]
    # equations = ["a!=i","g==k","k==j","k!=i","c!=e","a!=e","k!=a","a!=g","g!=c"]
    # equations = []
    print(S.equationsPossible(equations))
    print('done')
